// 6 堆排序
// 堆排序
// 时间复杂度是: O(n lg n)
// 空间原址性：任何时候都只需要常数个额外的元素空间存储临时数据。

/// （二叉）堆是一个近似完全二叉树，其中每个节点都大于等于其子节点。
/// 除了最底层外，该树是完全充满的;
/// 是从左向右填充.
/// 最大堆：结点的值至多与其父结点一样大。
/// A[PARENT(i)]>=A[i]
pub struct Heap<T: PartialOrd + Clone + Default> {
    heap_size: usize,
    data: Vec<T>,
}

impl<T: PartialOrd + Clone + Default> Heap<T> {
    pub fn new() -> Self {
        Heap {
            heap_size: 0,
            data: vec![],
        }
    }

    pub fn length(&self) -> usize {
        self.data.len()
    }

    /// 父节点索引
    /// 参数：
    /// i: 子节点的索引
    pub fn parent(&self, i: usize) -> usize {
        return (i - 1) / 2;
    }

    /// 左节点索引
    /// 参数：
    /// i: 父节点的索引
    pub fn left(&self, i: usize) -> usize {
        return 2 * i + 1;
    }

    /// 右节点索引
    /// 参数：
    /// i: 父节点的索引
    pub fn right(&self, i: usize) -> usize {
        return 2 * i + 2;
    }

    /// 最大堆插入
    pub fn max_heap_insert(&mut self, key: T) {
        self.heap_size += 1;
        self.data.push(T::default());
        self.heap_increase_key(self.data.len() - 1, key);
    }

    /// 最大堆化
    fn max_heapify(&mut self, i: usize) {
        let left = self.left(i);
        let right = self.right(i);
        let mut largest = i;

        if left < self.heap_size && self.data[left] > self.data[i] {
            largest = left;
        }

        if right < self.heap_size && self.data[right] > self.data[largest] {
            largest = right;
        }

        if largest != i {
            self.data.swap(i, largest);
            self.max_heapify(largest);
        }
    }

    /// 构建最大堆
    fn build_max_heap(&mut self) {
        for i in (0..self.data.len() / 2).rev() {
            self.max_heapify(i);
        }
    }

    /// 堆排序
    pub fn heap_sort(&mut self) {
        self.build_max_heap();
        for i in (1..self.data.len()).rev() {
            self.data.swap(0, i);
            self.heap_size -= 1;
            self.max_heapify(0);
        }
    }

    pub fn heap_maximum(&self) -> T {
        self.data[0].clone()
    }

    pub fn heap_extract_max(&mut self) -> T {
        let max = self.data[0].clone();
        self.data[0] = self.data[self.data.len() - 1].clone();
        self.data.pop();
        self.max_heapify(0);
        max
    }

    fn heap_increase_key(&mut self, index: usize, key: T) {
        self.data[index] = key;
        let mut i = index;
        while i > 0 && self.data[(i - 1) / 2] < self.data[i] {
            self.data.swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_heap_sort() {
        use crate::test_utils;
        let a = test_utils::gen_random_vec::<i32>(100);

        let mut heap = Heap::new();
        for i in a {
            heap.max_heap_insert(i);
        }

        heap.heap_sort();

        test_utils::assert_vec_asc(&heap.data);
    }

    #[test]
    fn test_heap_sort_book_sample() {
        let mut heap = Heap::new();
        heap.max_heap_insert(5);
        heap.max_heap_insert(13);
        heap.max_heap_insert(2);
        heap.max_heap_insert(25);
        heap.max_heap_insert(7);
        heap.max_heap_insert(17);
        heap.max_heap_insert(20);
        heap.max_heap_insert(8);
        heap.max_heap_insert(4);

        heap.heap_sort();

        assert_eq!(heap.data, vec![2, 4, 5, 7, 8, 13, 17, 20, 25]);
    }
}
